1795C - Tea Tasting - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll M = 1e9 + 7;

/*
        ***        **************
        ***        **************
        ***        ***
        ***        ***
        ***        ***
        *************************
        *************************
                   ***        ***
                   ***        ***
                   ***        ***
        **************        ***
        **************        ***

*/

#define v(li) vector<ll>
#define vp(li) vector<pair<ll, ll>>
#define m(li) map<ll, ll>
#define s(li) set<ll>

#define f(i, n) for (ll i = 0; i < n; i++)
#define f1(i, n) for (ll i = 1; i < n+1; i++)
#define test(t) while (t--)
#define w(i, n) while (i < n)
#define prs(n) cout << n << " "
#define prn(n) cout << n << " "
#define newl cout << "\n"
#define pb(a) push_back(a);
#define pop pop_back()
#define in(x) insert(x)
#define fsort(v) sort(v.begin(), v.end())
#define rsort(v) sort(v.begin(), v.end(), greater<ll>())
#define rev(v) reverse(v.begin(), v.end())
#define max_ele(v) *max_element(v.begin(), v.end())
#define min_ele(v) *min_element(v.begin(), v.end())

ll binexp(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binexp(a, b / 2);
    if (b % 2 == 0)
        return res * res;
    else
        return a * res * res;
}

ll biexm(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = biexm(a, b / 2);
    if (b % 2 == 0)
        return ((res % M) * (res % M)) % M;
    else
        return ((((res % M) * (res % M)) % M) * (a % M)) % M;
}

ll hcf(ll a, ll b)
{
    if (a % b == 0)
        return b;
    return hcf(b, a % b);
}
ll lcm(ll a,ll b){
    return (a*b)/(hcf(a,b));
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /* Sieve */
    // ll N=1e6;
    // ll spf[N+1];
    // f(i,N+1) spf[i]=i;
    // for(ll i=2;i<N+1;i++){
    //     if(spf[i]==i){
    //         for(ll j=i*i;j<N+1;j+=i){
    //            spf[j]=i;
    //         }
    //     }
    // }


    // ll N=1e6;
    // bool isprime[N+1];
    // f1(i,N) isprime[i]=true;
    // isprime[1]=false;
    // for(ll i=2;i<N+1;i++){
    //     if(isprime[i]){
    //         for(ll j=i*i;j<N+1;j+=i) isprime[j]=false;
    //     }
    // }


    // vector<ll> primes;
    // for(ll i=2;i<N+1;i++) if(isprime[i]) primes.push_back(i);


            /* Code Starts here */
    ll t;
    cin >> t;
    test(t)
    {   
        ll n;
        cin>>n;
        ll a[n+1];
        f1(i,n){
            cin>>a[i];
        }
        ll b[n+1];
        f1(i,n){
            cin>>b[i];
        }
        ll pre[n+1]={0};
        f1(i,n){
            pre[i]=pre[i-1]+b[i];
        }
        ll ans[n+2]={0};
        ll d[n+2]={0};
        ll ct=0;
        f1(i,n){
            ll l=i,r=n;
            ll ans1=n+1;
            while(l<=r){
                ll mid=(l+r)/2;
                ll s1=pre[mid]-pre[i-1];
                if(s1>=a[i]){
                    ans1=mid;
                    r=mid-1;
                }else l=mid+1;
            }
            ans[ans1]+=a[i]-(pre[ans1-1]-pre[i-1]);
            d[ans1]++;
            ct+=d[i];
            ans[i]+=(i-ct)*b[i];
        }
        f1(i,n) cout<<ans[i]<<" ";
        newl;
    }

    return 0;
}